package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ThreeSum {
	
//	public List<List<Integer>> threeSum(int[] nums) {
//		List<List<Integer>> resultList=new ArrayList<List<Integer>>();
//		if(nums.length<3)return resultList;
//		for(int i=0;i<nums.length-2;i++)
//			for(int j=i+1;j<nums.length-1;j++)
//				for(int k=j+1;k<nums.length;k++){
//					if((nums[i]+nums[j]+nums[k])==0){
//						List<Integer>now=new ArrayList<Integer>();
//						int array[]={nums[i],nums[j],nums[k]};
//						Arrays.sort(array);
//						boolean isHas=false;
//						if(resultList.size()>0)
//						for(List<Integer>list:resultList){
//							if(list.get(0)==array[0]
//									&&list.get(1)==array[1]
//									&&list.get(2)==array[2]){
//								isHas=true;
//								break;
//							}
//						}
//						if(!isHas){
//							now.add(Integer.valueOf(array[0]));
//							now.add(Integer.valueOf(array[1]));
//							now.add(Integer.valueOf(array[2]));
//							resultList.add(now);
//						}
//					}
//				}
//        return resultList;
//	 }
	
	
	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> resultList=new ArrayList<List<Integer>>();
		for(int i=0;i<nums.length-2;i++){
			if (i != 0 && nums[i] == nums[i - 1]) {  
                continue;  
            }  
			
			int l=i+1;
			int j=nums.length-1;
			while(l<j){
				if(nums[l]+nums[j]>0-nums[i]){
					j--;
				}else if(nums[l]+nums[j]<0-nums[i]){
					l++;
				}else{
					List<Integer>now=new ArrayList<Integer>();
					now.add(Integer.valueOf(nums[i]));
					now.add(Integer.valueOf(nums[l]));
					now.add(Integer.valueOf(nums[j]));
					resultList.add(now);
					l++;
					j--;
					while(l<j&&nums[l]==nums[l-1])l++;
					while(l<j&&nums[j]==nums[j+1])j--;
				}
			}
		}
		return resultList;
	}
	
}
